package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Subsets {

	public static void main(String[] args) {
		Subsets ins = new Subsets();
		
		int[] test1 = {1, 2, 3};
		List<List<Integer>> res1 = ins.subsets(test1);
		LeetCodeHelpers.printListOfList(res1);
	}
	
	public List<List<Integer>> subsets(int[] S) {
		List<List<Integer>> finalRes = new LinkedList<List<Integer>>();
		
		if (S == null || S.length == 0) return finalRes;
		Arrays.sort(S);
		
		List<Integer> res = new LinkedList<Integer>();
		helper(S, 0, finalRes, res);
		//subsetsHelper(finalRes, S, res, 0);
		return finalRes;
	}
	
	// this is 2^n, using bit operation
    public List<List<Integer>> subsetsMath(int[] S) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        
        if (S == null || S.length == 0) {
            return res;
        }
        
        Arrays.sort(S);
        
        for (int i = 0; i < Math.pow(2, S.length); ++i) {
            ArrayList<Integer> a = new ArrayList<Integer>();
            int index = 0;
            int n = i;
            while (n > 0) {
                if ((n & 1) == 1) {
                    a.add(S[index]);
                }
                index++;
                n = n >> 1;
            }
            res.add(a);
        }
        
        return res;
    }
	
	private void helper(int[] s, int start, List<List<Integer>> finalRes, List<Integer> res) {
		// every recursion step is a solution
		finalRes.add(new LinkedList<Integer>(res));
		
		for (int i = start; i < s.length; i++) {
			res.add(s[i]);
			helper(s, i + 1, finalRes, res);
			res.remove(res.size() - 1);
		}
	}
	
	// TODO: look into the recursion solution and N elements choose K.
	private void subsetsHelper(List<List<Integer>> res, int[] S, List<Integer> tmp, int level) {
        if (level == S.length) {
            ArrayList<Integer> n = new ArrayList<Integer>();
            n.addAll(tmp);
            res.add(n);
            return;
        }
        
        // in order traversal, current element not included
        subsetsHelper(res, S, tmp, level + 1);
        
        tmp.add(S[level]);
        // current element included
        subsetsHelper(res, S, tmp, level + 1);
        
        tmp.remove(tmp.size() - 1);
    }
	
}
